def matrix_chain_order(p):  
    n = len(p) - 1  # 矩阵数量  
    m = [[0 for _ in range(n+1)] for _ in range(n+1)]  
    s = [[0 for _ in range(n+1)] for _ in range(n+1)]  
  
    # m[i,j] = Minimum number of multiplications in A[i]A[i+1]...A[j]  
    for l in range(2, n+1):  # l 是链的长度  
        for i in range(1, n-l+2+1):  
            j = i + l - 1  
            m[i][j] = float('inf')  
            for k in range(i, j):  
                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j]  
                if q < m[i][j]:  
                    m[i][j] = q  
                    s[i][j] = k  
  
    # 输出结果  
    def print_optimal_parens(s, i, j):  
        if i == j:  
            print(f"A{i}", end="")  
        else:  
            print("(", end="")  
            print_optimal_parens(s, i, s[i][j])  
            print_optimal_parens(s, s[i][j] + 1, j)  
            print(")", end="")  
  
    with open('input.txt', 'r') as file:  
        lines = file.readlines()  
        matrix_dims = []  
        for line in lines:  
            parts = line.split('×')  
            matrix_name, dim1, dim2 = parts[0].strip(), int(parts[1]), int(parts[2])  
            matrix_dims.append(dim1)  
            matrix_dims.append(dim2)  
  
    print(f"Minimum number of multiplications is {m[1][n]}")  
    with open('output.txt', 'w') as file:  
        file.write(f"Minimum number of multiplications is {m[1][n]}\n")  
        file.write("Optimal parenthesization is:\n")  
        print_optimal_parens(s, 1, n)  
        file.write(f" {print_optimal_parens(s, 1, n).strip()}\n")  
